#---------------------------[知乎：叶枝黎曼]---------------------------
'''
幼儿园里有 N 个小朋友，老师现在想要给这些小朋友们分配糖果，要求每个小朋友都要分到糖果。

但是小朋友们也有嫉妒心，总是会提出一些要求，比如小明不希望小红分到的糖果比他的多，于是在分配糖果的时候， 老师需要满足小朋友们的 K 个要求。

幼儿园的糖果总是有限的，老师想知道他至少需要准备多少个糖果，才能使得每个小朋友都能够分到糖果，并且满足小朋友们所有的要求。

输入格式
输入的第一行是两个整数 N,K。

接下来 K 行，表示分配糖果时需要满足的关系，每行 3 个数字 X,A,B。

如果 X=1．表示第 A 个小朋友分到的糖果必须和第 B 个小朋友分到的糖果一样多。
如果 X=2，表示第 A 个小朋友分到的糖果必须少于第 B 个小朋友分到的糖果。
如果 X=3，表示第 A 个小朋友分到的糖果必须不少于第 B 个小朋友分到的糖果。
如果 X=4，表示第 A 个小朋友分到的糖果必须多于第 B 个小朋友分到的糖果。
如果 X=5，表示第 A 个小朋友分到的糖果必须不多于第 B 个小朋友分到的糖果。
小朋友编号从 1 到 N。

输出格式
输出一行，表示老师至少需要准备的糖果数，如果不能满足小朋友们的所有要求，就输出 −1。

数据范围
1≤N<105,
1≤K≤105,
1≤X≤5,
1≤A,B≤N
输入样例：
5 7
1 1 2
2 3 2
4 4 1
3 4 5
5 4 5
2 3 5
4 5 1
输出样例：
11
'''

def Lin(a,b,c):
    if a not in link.keys():
        link[a] = {b:c}
    else:
        if b not in link[a].keys():
            link[a].update({b:c})
        else:
            link[a][b] = max(link[a][b],c)

def SPFA(start):
    queue = [start]
    dis[start] = 0
    inq  = [False]*(n + 1) 
    inq[start] = True
    cnt = [0]*(n + 1)
    while queue:
        curNode = queue.pop(0)
        inq[curNode] = False
        if curNode not in link.keys():
            continue

        for node in link[curNode].keys():
            cnt[node] += 1
            if dis[curNode] + link[curNode][node] > dis[node]:
                if cnt[node] >= n + 1:
                    return False #存在负环
                dis[node] = dis[curNode] + link[curNode][node]
                if inq[node] == False:
                    inq[node] = True
                    queue.append(node)

    return True
n,k = map(int,input().split())
link = {}
for i in range(k):
    x,a,b = map(int,input().split())
    if x == 1:
        Lin(a,b,0)
        Lin(b,a,0)
    if x == 2:
        Lin(a,b,1)
    if x == 3:
        Lin(b,a,0)
    if x == 4:
        Lin(b,a,1)
    if x == 5:
        Lin(a,b,0)

for i in range(1,n+1): #超级源点
    Lin(0,i,1)

dis = [-float('inf')]*(n + 1)
if SPFA(0):
    res = 0
    for i in range(1,n+1):
        res += dis[i]
    print(res)
else:
    print(-1)
